SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Algorithmic Puzzles</title>

</head>

Algorithmic Puzzles

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1287740527">

/* start https://en.wikipedia.org/ */

.mw-parser-output .ib-book .infobox-title{font-style:italic;padding-bottom:0.2em}.mw-parser-output .ib-book .Z3988{display:none}.mw-parser-output .ib-book .infobox-below{border-top:#aaa 1px solid}

/* end https://en.wikipedia.org/ */

</style><table class="infobox ib-book vcard"><caption class="infobox-title">Algorithmic Puzzles </caption><tbody><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">First edition</div></td></tr><tr><th scope="row" class="infobox-label">Author</th><td class="infobox-data">Anany Levitin, Maria Levitin</td></tr><tr><th scope="row" class="infobox-label">Publisher</th><td class="infobox-data"><a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a></td></tr><tr><th scope="row" class="infobox-label"><div style="display: inline-block; line-height: 1.2em; padding: .1em 0;">Publication date</div></th><td class="infobox-data">2011</td></tr></tbody></table>

Algorithmic Puzzles is a book of puzzles based on <a href="Computational_thinking" title="Computational thinking">computational thinking</a>. It was written by computer scientists Anany and Maria Levitin, and published in 2011 by <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>.

<div class="mw-heading mw-heading2"><h2 id="Topics">Topics</h2></div>

The book begins with a "tutorial" introducing classical algorithm design techniques including <a href="Backtracking" title="Backtracking">backtracking</a>, <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer algorithms</a>, and <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>, methods for the <a href="Analysis_of_algorithms" title="Analysis of algorithms">analysis of algorithms</a>, and their application in example puzzles.<a href="#cite_note-gasarch-1">[1]</a><a href="#cite_note-rosebrock-2">[2]</a> The puzzles themselves are grouped into three sets of 50 puzzles, in increasing order of difficulty. A final two chapters provide brief hints and more detailed solutions to the puzzles,<a href="#cite_note-rosebrock-2">[2]</a> with the solutions forming the majority of pages of the book.<a href="#cite_note-griffiths-3">[3]</a>

Some of the puzzles are well known classics, some are variations of known puzzles making them more algorithmic, and some are new.<a href="#cite_note-narayanan-4">[4]</a> They include:

<ul><li>Puzzles involving chessboards, including the <a href="Eight_queens_puzzle" title="Eight queens puzzle">eight queens puzzle</a>, <a href="Knight's_tour" title="Knight's tour">knight's tours</a>, and the <a href="Mutilated_chessboard_problem" title="Mutilated chessboard problem">mutilated chessboard problem</a><a href="#cite_note-gasarch-1">[1]</a><a href="#cite_note-griffiths-3">[3]</a><a href="#cite_note-narayanan-4">[4]</a></li>

<li><a href="Balance_puzzle" title="Balance puzzle">Balance puzzles</a><a href="#cite_note-griffiths-3">[3]</a></li>

<li><a href="River_crossing_puzzle" title="River crossing puzzle">River crossing puzzles</a><a href="#cite_note-griffiths-3">[3]</a><a href="#cite_note-narayanan-4">[4]</a></li>

<li>The <a href="Tower_of_Hanoi" title="Tower of Hanoi">Tower of Hanoi</a><a href="#cite_note-narayanan-4">[4]</a></li>

<li>Finding the missing element in a <a href="Streaming_algorithm" title="Streaming algorithm">data stream</a><a href="#cite_note-gasarch-1">[1]</a></li>

<li>The <a href="Geometric_median" title="Geometric median">geometric median</a> problem for <a href="Manhattan_distance" class="mw-redirect" title="Manhattan distance">Manhattan distance</a><a href="#cite_note-gasarch-1">[1]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Audience_and_reception">Audience and reception</h2></div>

The puzzles in the book cover a wide range of difficulty, and in general do not require more than a high school level of mathematical background.<a href="#cite_note-griffiths-3">[3]</a>

<a href="William_Gasarch" title="William Gasarch">William Gasarch</a> notes that grouping the puzzles only by their difficulty and not by their themes is actually an advantage, as it provides readers with fewer clues about their solutions.<a href="#cite_note-gasarch-1">[1]</a>

Reviewer Narayanan Narayanan recommends the book to any puzzle aficionado, or to anyone who wants to develop their powers of algorithmic thinking.<a href="#cite_note-narayanan-4">[4]</a> Reviewer Martin Griffiths suggests another group of readers, schoolteachers and university instructors in search of examples to illustrate the power of algorithmic thinking.<a href="#cite_note-griffiths-3">[3]</a>

Gasarch recommends the book to any computer scientist, evaluating it as "a delight".<a href="#cite_note-gasarch-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGasarch2013" class="citation cs2"><a href="William_Gasarch" title="William Gasarch">Gasarch, William</a> (December 2013), <a rel="nofollow" class="external text" href="https://www.cs.umd.edu/~gasarch/bookrev/44-4.pdf">"Review of Algorithmic Puzzles"</a> (PDF), ACM SIGACT News, 44 (4): 47–48, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2556663.2556674">10.1145/2556663.2556674</a></cite>

</li>

<li id="cite_note-rosebrock-2">^ <a href="#cite_ref-rosebrock_2-0">a</a> <a href="#cite_ref-rosebrock_2-1">b</a> <cite id="CITEREFRosebrock" class="citation cs2">Rosebrock, Stephan, "Review of Algorithmic Puzzles", zbMATH, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1233.00005">1233.00005</a></cite>

</li>

<li id="cite_note-griffiths-3">^ <a href="#cite_ref-griffiths_3-0">a</a> <a href="#cite_ref-griffiths_3-1">b</a> <a href="#cite_ref-griffiths_3-2">c</a> <a href="#cite_ref-griffiths_3-3">d</a> <a href="#cite_ref-griffiths_3-4">e</a> <a href="#cite_ref-griffiths_3-5">f</a> <cite id="CITEREFGriffiths2014" class="citation cs2">Griffiths, Martin (March 2014), "Review of Algorithmic Puzzles", The Mathematical Gazette, 98 (541): 188, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0025557200001182">10.1017/S0025557200001182</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/24496640">24496640</a></cite>

</li>

<li id="cite_note-narayanan-4">^ <a href="#cite_ref-narayanan_4-0">a</a> <a href="#cite_ref-narayanan_4-1">b</a> <a href="#cite_ref-narayanan_4-2">c</a> <a href="#cite_ref-narayanan_4-3">d</a> <a href="#cite_ref-narayanan_4-4">e</a> <cite id="CITEREFNarayanan2012" class="citation cs2">Narayanan, Narayanan (2012), "Review of Algorithmic Puzzles", Mathematical Reviews, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2866446">2866446</a></cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-28" href="https://en.wikipedia.org/wiki/?title=Algorithmic_Puzzles&oldid=1282780285">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>